package com.novice.com.novice.algorithm;

/**
 * 二分查找: 有序数组，查询target 返回索引值
 * 找不到返回-1
 * <P>
 * ## 整体思路：
 * <p>
 * 1.首先设置了i、j两个指针，这两个指针呢，指向的是这个数字的两端，
 * <p>
 * 2.当i在j的左侧，或者是它俩相等的时候，就循环来执行逻辑，
 * <p>
 * 3.然后i在j的右侧，表示没有找到，返回失败的结果
 * <p>
 * 4.中间这个循环，就是取i和j的中间值，把它的中间值跟目标值进行一个比较，
 * <p>
 * 5.如果目标在中间值的左侧，接下来还应该在左边找，所以让右边界缩小到中间索引减一位置，
 * <p>
 * 6.如果目标在中间值的右侧，目标在右侧，就改变左边界，让它增大成为中间索引位置右边一个位置，
 * <p>
 * 7.循环缩小范围，直到中间值跟目标值相等，返回这个中间索引
 *
 * @author novice
 * @Date 2024/03/31
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int target = 1;
        int index = binarySearch(arr, target);
        System.out.println(index);
    }

    /**
     * 二分查找
     *
     * @param arr    加勒比海盗
     * @param target 目标
     * @return int
     */
    private static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) { // 正合适
                return mid;
            } else if (arr[mid] < target) { // 中间值小于目标值，说明目标值在右边
                left = mid + 1;
            } else if(arr[mid] > target){ // 中间值大于目标值，说明目标值在左边
                right = mid - 1;
            }
        }
        return -1;
    }
}
